//Mobius bzoj2301 O(N+Q*sqrt(N))
LL solve(int n,int m){
	LL res=0;
	if (n>m) swap(n,m);
	for (int i=1,l=0; i<=n; i=l+1){
		l=min(n/(n/i),m/(m/i));
		res+=1ll*(sum[l]-sum[i-1])*(n/i)*(m/i);
	}
	return res;
}

int main(){
	Mobius();
	for (scanf("%d",&T); T--; ){
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		LL ans=solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)+solve((a-1)/k,(c-1)/k);
		printf("%lld\n",ans);
	}
	return 0;
}

//杜教筛：http://www.cnblogs.com/y-clever/p/6514901.html
//O(Q*N^3/4),预处理O(Q*N^2/3)
//n^2/3粗略计算方法：b^2/3=a -> a^3/2=b -> (sqrt(a))^3=b
#include<map>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (register int i=l; i<=r; ++i)
typedef long long ll;
typedef std::map<int,ll> Map;
using namespace std;

Map Phi,Miu;
const int N=5000100;
ll phi[N],miu[N];
int p[N/5],n;

void init(int n){
   memset(phi,-1,sizeof(phi));
   memset(miu,-1,sizeof(miu));
   int tot=0; miu[0]=phi[0]=0; miu[1]=phi[1]=1;
   rep(i,2,n){
      if (phi[i]==-1) p[++tot]=i,phi[i]=i-1,miu[i]=-1;
      for (int j=1; j<=tot && p[j]*i<=n; j++){
         if (i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1),miu[i*p[j]]=-miu[i];
         else { phi[i*p[j]]=phi[i]*p[j]; miu[i*p[j]]=0; break; }
      }
      phi[i]+=phi[i-1]; miu[i]+=miu[i-1];
   }
}

ll cPhi(ll n){
   Map::iterator it;
   if (n<N) return phi[n];
   if ((it=Phi.find(n))!=Phi.end()) return it->second;
   ll lst,ans=(1ll*n*(n+1))>>1;
   for (ll i=2; i<=n; i=lst+1) lst=n/(n/i),ans-=(lst-i+1)*cPhi(n/i);
   return Phi[n]=ans;
}

ll cMiu(ll n){
   Map::iterator it;
   if (n<N) return miu[n];
   if ((it=Miu.find(n))!=Miu.end()) return it->second;
   ll lst,ans=1;
   for (ll i=2; i<=n; i=lst+1) lst=n/(n/i),ans-=(lst-i+1)*cMiu(n/i);
   return Miu[n]=ans;
}

int main(){
   freopen("bzoj3944.in","r",stdin);
   freopen("bzoj3944.out","w",stdout);
   init(N-1); int T;
   for (scanf("%d",&T); T--; ) scanf("%d",&n),printf("%lld %lld\n",cPhi(n),cMiu(n));
   return 0;
}